#!/usr/bin/env python3

"""
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed)
parentheses substring.
"""

class Solution:
    def longest_valid_parentheses(self, string):
        result = 0
        current = 0
        left_sub_right = 0
        for ch in string:
            if ch == ')':
                left_sub_right -= 1
                if left_sub_right >= 0:
                    current += 1
            else:
                left_sub_right += 1

            if left_sub_right < 0:
                result = max(result, current)
                current = 0
                left_sub_right = 0
            elif left_sub_right == 0:
                result = max(result, current)

        if current > result:
            # need right to left
            right_sub_left = 0
            current = 0
            for index in range(len(string) - 1, -1, -1):
                ch = string[index]
                if ch == '(':
                    right_sub_left -= 1
                    if right_sub_left >= 0:
                        current += 1
                else:
                    right_sub_left += 1
                
                if right_sub_left < 0:
                    result = max(result, current)
                    current = 0
                    right_sub_left = 0
                elif right_sub_left == 0:
                    result = max(result, current)
        result *= 2
        return result


if __name__ == '__main__':
    solution = Solution()
    assert 10 == solution.longest_valid_parentheses(")()(((())))(")
    assert 2 == solution.longest_valid_parentheses('()')
    assert 2 == solution.longest_valid_parentheses('(()')
    assert 4 == solution.longest_valid_parentheses(')()())')
    assert 2 == solution.longest_valid_parentheses('()(()')
